在電腦之中，數值都是已二進位去做儲存
對於數值來說有些運算可以透過位元運算來達到優化
因為位元運算相對於數值運算效率高許多
常見的位元運算有以下幾個
XOR 具有把相同數值的 bit 歸零的效果
這個特性可以用來尋找一個連續數列中消失的值
假設有一個整數陣列 arr 長度 n 其中每個值 arr[i] 其值介於 [0, n]
且每個值是唯一出現
要求找出不存在 0 到 n 中不存在陣列 arr 的值
已知對任何數值 a
a XOR 0 = 0 XOR a = a
a XOR a = 0
所以可以透過
把陣列中所有值都先 XOR 起來到一個數值 result
然後把依序把 0 到 n 對 result 做 XOR
因為如果成對出現就會變成 0, 而 0 XOR 其他數值則會保存原本那個數值
所以沒成對出現的數就會剩下來
iThome鐵人賽
看影片追技術